public class SolutionOffer37 {

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    public String serialize(TreeNode root) {
        if (root==null){
            return "";
        }
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append(root.val);
        stringBuilder.append('(');
        stringBuilder.append(serialize(root.left));
        stringBuilder.append(")(");
        stringBuilder.append(serialize(root.right));
        stringBuilder.append(')');
        return stringBuilder.toString();
    }

    public TreeNode deserialize(String data) {
        if (data.length()==0){
            return null;
        }
        int count=0,rec=-1;
        char[] chars=data.toCharArray();
        for (int i=0;i<chars.length;i++) {
            if (chars[i]=='('){
                count++;
            }
            if (chars[i]==')'){
                count--;
                if (count==0){
                    rec=i;
                    break;
                }
            }
        }
        int t=data.indexOf('(');
        TreeNode treeNode=new TreeNode(Integer.parseInt(data.substring(0,t)));
        treeNode.left=deserialize(data.substring(t+1,rec));
        treeNode.right=deserialize(data.substring(rec+2,data.length()-1));
        return treeNode;
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode n1=new TreeNode(2);
        TreeNode n2=new TreeNode(3);
        TreeNode n3=new TreeNode(4);
        TreeNode n4=new TreeNode(5);
        n2.left=n3;
        n2.right=n4;
        root.left=n1;
        root.right=n2;
        String temp=new SolutionOffer37().serialize(root);
        System.out.println(temp);
        TreeNode treeNode=new SolutionOffer37().deserialize(temp);
        System.out.println(treeNode.right.right.val);
    }
}
